package Test;

import java.util.List;
/*

 */
public class 排序链表 {
    public ListNode sortList(ListNode head) {
       return head==null?null:mergeList(head);


       }
       ListNode mergeList(ListNode head){
        if(head.next==null) return head;
        ListNode slow,fast,pre;
        slow=fast=head;
        pre=null;
        //求出中点
        while (fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        //进行分解，直到分解到一个节点为止
        ListNode left=mergeList(head);
        ListNode right=mergeList(slow);
        return merge(left,right);
    }
    ListNode merge(ListNode left,ListNode right){

        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        while (left!=null&&right!=null){
            if(left.val<right.val){
                cur.next=left;
                left=left.next;
            }else {
                cur.next=right;
                right=right.next;
            }
            cur=cur.next;
        }
        if(left!=null){
            cur.next=left;
        }
        if(right!=null){
            cur.next=right;
        }
        return dummy.next;
    }
}
